/**
 * https://leetcode.cn/problems/snakes-and-ladders/submissions/584645625/
 * 909. 蛇梯棋
 * medium 陈贝纯 2024.12.03
 * bfs
 */

class Solution {
public:
    int h=0;
    int l=0;
    int n=0;
    void js(int t){
        h=t/n;
        if(t%n)
            h++;
        if(h%2){
            if(t%n)
                l=t%n-1;
            else
                l=n-1;
        }
        else{
            if(t%n)
                l=n-t%n;
            else
                l=0;
        }
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        queue<int> q;
        n=board.size();
        int g=n*n;
        vector<int> vist(g+1,true);
        for(int i=2;i<8&&i<=g;++i){
            js(i);
            if(board[n-h][l]!=-1)
                q.push(board[n-h][l]);
            else
                q.push(i);
        }
        int walk=0;
        while(!q.empty()){
            walk++;
            int k=q.size();
            while(k--){
                int t=q.front();
                q.pop();
                if(t==g)
                    return walk;
                for(int i=1;i<7&&t+i<=g;++i){
                    if(vist [i+t]){
                        vist[i+t]=false;
                        js(t+i);
                    if(board[n-h][l]!=-1)
                        q.push(board[n-h][l]);
                    else
                        q.push(t+i);
                    }
                }
            }
        }
        return -1;
    }
};